A Closure for 1-Hamilton-Connectedness in Claw-Free Graphs

Title: A Closure for 1-Hamilton-Connectedness in Claw-Free Graphs
Creator: Ryjáček, Zdeněk; Vrána, Petr
Relation: Journal of Graph Theory Vol. 75, Issue 4, p. 358-376
Publisher Link: http://dx.doi.org/10.1002/jgt.21743
Publisher: Wiley Blackwell Publishing
Resource Type: journal article
Date: 2014
Description: A graph G is 1-Hamilton-connected if G-x is Hamilton-connected for every vertex x∈V(G). In the article, we introduce a closure concept for 1-Hamilton-connectedness in claw-free graphs. If G¯ is a (new) closure of a claw-free graph G, then G¯ is 1-Hamilton-connected if and only if G is 1-Hamilton-connected, G¯ is the line graph of a multigraph, and for some x∈V(G), G¯-x is the line graph of a multigraph with at most two triangles or at most one double edge. As applications, we prove that Thomassen's Conjecture (every 4-connected line graph is hamiltonian) is equivalent to the statement that every 4-connected claw-free graph is 1-Hamilton-connected, and we present results showing that every 5-connected claw-free graph with minimum degree at least 6 is 1-Hamilton-connected and that every 4-connected claw-free and hourglass-free graph is 1-Hamilton-connected.
Identifier: http://hdl.handle.net/1959.13/1067584
Identifier: uon:18443
Identifier: ISSN:1097-0118
Language: eng
Reviewed

		Thumbnail	File	Description	Size	Format